package cn.hy.leetcode;

import cn.hy.entity.ListNode;
import cn.hy.util.StringUtil;
import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.stream.Collectors;

/**
 * LeetCode算法题解法
 * @author 何轶
 */
@Slf4j
public class Solution {

    /**
     * 2. 两数相加
     * 给你两个<strong>非空</strong>的链表，表示两个非负的整数。它们每位数字都是按照<strong>逆序</strong>的方式存储的，并且每个节点只能存储<strong>一位</strong>数字。
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * 你可以假设除了数字<strong>0</strong>之外，这两个数都不会以<strong>0</strong>开头。
     * @param l1 链表1
     * @param l2 链表2
     * @return 相加后的值
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(-1);
        // 头指针
        ListNode pointer = new ListNode(-1, result);
        // l1、l2和的进位
        int redundant = 0;

        while (l1 != null || l2 != null) {
            // 通过指针赋值
            int sum = (l1==null?0:l1. val) + (l2==null?0:l2. val) + redundant;
            pointer.next.val = sum % 10;
            pointer.next.next = new ListNode(-1);
            pointer.next = pointer.next.next;
            redundant = sum>9 ? sum / 10 : 0;

            // l1 l2 指针往后移一位
            l1 = l1==null?null:l1.next;
            l2 = l2==null?null:l2.next;
        }

        // 最后一位如果有进位则新建一个节点
        if (redundant >= 10) {
            pointer.next.val = redundant % 10;
            pointer.next.next = new ListNode(redundant / 10);
            pointer.next = pointer.next.next;
        } else if (redundant > 0){
            pointer.next.val = redundant;
        }

        // 判断result最后是否有空节点, 有的话去掉
        pointer = result;
        while (pointer != null) {
            if (pointer.next != null && pointer.next.val == -1) {
                pointer.next = null;
                break;
            }
            pointer = pointer.next;
        }

        return result;
    }

    /**
     * 3. 无重复字符的最长子串<br/>
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     * @param s 模板字符串
     * @return 不重复的最长子串长度
     */
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> substring = new HashMap<>();
//        Set<Character> substring = new HashSet<>();
        char[] sChar = s.toCharArray();
        int sCharLen = sChar.length, index = 0;
        List<Integer> lengths = new ArrayList<>();

        // 遍历由模板字符串转成的字符数组
        for (; index < sCharLen; index++) {
            // 当前元素
            char c = sChar[index];

            // 判断 HashMap 中是否存在当前元素的key, 如果存在说明重复
            if (!substring.containsKey(c)) {
                // 将当前元素存入HashSet, 如果与之前的元素是非重复的则长度会+1, 否则长度不变, 可通过这个特性来判断是否重复了
                substring.put(c, index);
            } else {
                // 遇到重复字符, 进入重复字符的处理逻辑
                int length = substring.size();

                // 保存当前子串长度
                lengths.add(length);

                // 取得当前子串中与当前元素重复的字符的位置的下一个元素的位置(如a、b、c、a, 取得b的位置)
                // (+1 再 -1) 是因为重复字符位置+1才是下一个子串的首字符位置
                // -1 是因为完成这轮循环后index还有个自增1会导致指针移动到重复字符的下下个字符的位置
                index = substring.get(c) + 1 - 1;

                // 清除之前的结果
                substring = new HashMap<>();
            }
        }
        // 保存最后一次的结果
        lengths.add(substring.size());

        return lengths.stream().max(Integer::compare).orElse(0);
    }

    /**
     * 4. 寻找两个正序数组的中位数<br/>
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。<br/>
     * 算法的时间复杂度应该为 O(log (m+n))</br>
     * @param nums1 数组1
     * @param nums2 数组2
     * @return 两个数组的中位数
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int nums1Len = nums1.length;
        int nums2Len = nums2.length;
        int nums3Len = (nums1Len + nums2Len) / 2;
        int[] nums3 = new int[]{};

        int mp = 0;
        int np = 0;
        for (int index = 0; index <= (nums1Len + nums2Len) / 2; index++) {
            if (mp < nums1Len && np < nums2Len) {
                if (nums1[mp] > nums2[np]) {
                    nums3[index] = nums2[np++];
                } else {
                    nums3[index] = nums1[mp++];
                }
            } else if (mp > nums1Len){
                int more = (nums1Len + nums2Len) - nums3.length;
            }
        }

        return (nums1Len + nums2Len)%2 == 0
                ? (nums3[nums3.length-2] + nums3[nums3.length-1]) / 2.0
                : nums3[nums3.length-1];
    }

    /**
     * 212.单词搜索Ⅱ
     *      给定一个m x n 二维字符网格board和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
     *      单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
     *      同一个单元格内的字母在一个单词中不允许被重复使用。
     *      示例 1：
     *          输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
     *          输出：["eat","oath"]
     */
    public List<String> findWords(char[][] board, String[] words) {
        int wordsIndex = 0;
        int m = board.length;
        int n = board[0].length;
        List<Character> fakeStack = new LinkedList();
        while (wordsIndex < words.length) {
            char[] tmp = words[wordsIndex++].toCharArray();
            int cIndex = 0, i = 0, j = 0;
            for (;i<m && j<n;){
                System.out.print(board[i++][j++] + " ");
            }
        }
        return null;
    }

    /**
     * 240.编写一个高效的算法来搜索 m * x 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
     *      每行的元素从左到右升序排列。
     *      每列的元素从上到下升序排列。
     * @param matrix 大小为 m * x 的矩阵
     * @param target 要查找的目标值
     * @return true|false
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] m : matrix) {
            int left = 0;
            int mid = m.length / 2;
            while (left < mid) {
                if (target > m[mid]) {
                    left = mid;
                    mid = (m.length - left) / 2;
                } else if (target == m[mid]) {
                    return true;
                } else {
                    mid /= 2;
                }
                if (left == mid) {
                    if(target == m[mid]){
                        return true;
                    }
                    continue;
                }
            }
        }
        return false;
    }

    /**
     * 500. 键盘行
     * 给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。
     * @param words 传入的字符串数组
     * @return 符合条件的单词数组
     */
    public String[] findWords(String[] words){
        String[] result = new String[]{};
        List<String> resultList = new ArrayList<>(words.length);
        List<Character> rowTop = Arrays.asList(new Character[]{'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'});
        List<Character> rowMid = Arrays.asList(new Character[]{'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'});
        List<Character> rowBottom = Arrays.asList(new Character[]{'z', 'x', 'c', 'v', 'b', 'n', 'm'});
        List[] rows = new List[]{rowTop, rowMid, rowBottom};

        step1:
        for (String word : words) {
            String tmp = word.toLowerCase();
            int rowNum = rowTop.contains(tmp.charAt(0)) ? 0 :
                    rowMid.contains(tmp.charAt(0)) ? 1 :
                    rowBottom.contains(tmp.charAt(0)) ? 2 : -1;
            if (rowNum == -1) {
                System.err.println("illegal word: " + word);
                continue;
            }
            for (int i = 1; i < tmp.length(); i++) {
                if (!rows[rowNum].contains(tmp.charAt(i))){
                    continue step1;
                }
            }
            resultList.add(word);
        }
        return resultList.toArray(result);
    }

    /**
     * 541. 反转字符串
     *      给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。
     *           如果剩余字符少于 k 个，则将剩余字符全部反转。
     *           如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
     * @param s 待翻转的字符串
     * @param k 标定长度
     * @return 处理好的字符串
     */
    public String reverseStr2(String s, int k){
        String result = new String();
        for (int i = 0; i <= s.length(); i += 2*k) {
            String tmp = i+2*k <= s.length() ? s.substring(i, i+2*k) : s.substring(i);
            if (tmp.length() <= 2*k && tmp.length() > k) {
                tmp = StringUtil.reverse(tmp.substring(0, k)) + tmp.substring(k);
                result += tmp;
            } else {
                result += StringUtil.reverse(tmp);
            }
        }
        return result;
    }

    /**
     * 732. 我的课程安排表Ⅲ
     *
     * <p>当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。</p>
     * <p>给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。</p>
     * <p>实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。</p>
     * <li>MyCalendarThree() 初始化对象。</li>
     * <li>int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。</li>
     */
    public static class MyCalendarThree {
        private final ArrayList<Integer> startList;
        private final ArrayList<Integer> endList;
        private int maxRepeat = 0;

        public MyCalendarThree() {
            this.startList = new ArrayList<>();
            this.endList = new ArrayList<>();
        }

        public int book(int start, int end) {
            int currentRepeat = 1;

            for (int index=0; index < startList.size(); index++) {
                if (! (start > endList.get(index) || end <= startList.get(index))) {
                    // 有日期重复的
                    currentRepeat++;
                }
            }

            startList.add(start);
            endList.add(end);

            this.maxRepeat = Math.max(currentRepeat, this.maxRepeat);

            return this.maxRepeat;
        }
    }
    public MyCalendarThree getMyCalendarThreeInstance() {
        return new MyCalendarThree();
    }

    /**
     * 748.最短补全词
     * 给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出并返回 words 中的 最短补全词 。
     * 补全词 是一个包含 licensePlate 中所有的字母的单词。在所有补全词中，最短的那个就是 最短补全词 。
     * @param licensePlate 匹配字符串
     * @param words 待匹配的字符串数组
     * @return 匹配结果
     */
    public String shortestCompletingWord(String licensePlate, String[] words) {
        List<String> template = Arrays.asList(licensePlate.toLowerCase().replaceAll("[^a-z]", "").split(""));
        List<String> collect = Arrays.stream(words).map( word -> {
                List<String> tmp = new LinkedList<>(template);
                Arrays.stream(word.split("")).forEach(tmp::remove);
                if (tmp.size() <= 0) {
                    return word;
                }
                return "";
            }
        ).collect(Collectors.toList());
        collect.removeIf(""::equals);
        return collect.stream().min(Comparator.comparingInt(String::length)).orElse("");
    }

    /**
     * 807. 保持城市天际线<br/>
     * 给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。<br/>
     * 城市的 天际线 是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。<br/>
     * 我们被允许为 任意数量的建筑物 的高度增加 任意增量（不同建筑物的增量可能不同） 。 高度为 0 的建筑物的高度也可以增加。然而，增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。<br/>
     * 在 不改变 从任何主要方向观测到的城市 天际线 的前提下，返回建筑物可以增加的 最大高度增量总和 。<br/>
     * @param grid 城市建筑矩阵
     * @return 最高增量总和
     */
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int[] colMax = new int[grid.length];
        int[] rowMax = new int[grid.length];
        int totalAdd = 0;

        long startTime = System.currentTimeMillis();
        // 先寻找行列的最大值
        for (int outIndex=0; outIndex<grid.length; outIndex++) {

            int[] tmp = grid[outIndex];

            for (int inIndex=0; inIndex<tmp.length; inIndex++) {

                if (colMax[outIndex] < tmp[inIndex]) {
                    colMax[outIndex] = tmp[inIndex];
                }

                if (rowMax[inIndex] < tmp[inIndex]) {
                    rowMax[inIndex] = tmp[inIndex];
                }
            }

        }

        for (int outIndex=0; outIndex<grid.length; outIndex++) {

            for (int inIndex = 0; inIndex < grid[outIndex].length; inIndex++) {
                int currItem = grid[outIndex][inIndex];
                if (currItem < rowMax[inIndex] && currItem < colMax[outIndex]) {
                    totalAdd += rowMax[inIndex] < colMax[outIndex]
                            ? rowMax[inIndex] - currItem
                            : colMax[outIndex] - currItem;
                }

            }

        }

        System.out.println(System.currentTimeMillis() - startTime + "ms");
        return totalAdd;
    }

    /**
     * 878. 第N个神奇数字
     *      如果正整数可以被 A 或 B 整除，那么它是神奇的。
     *      返回第 N 个神奇数字。由于答案可能非常大，返回它模 10^9 + 7 的结果。
     * @return 计算结果 MOD 10^9 + 7 的结果
     */
    public int nthMagicalNumber(int n, int a, int b) {
        long mod = (long)Math.pow(10, 9) + 7;
        int index = a>b ? b-1 : a-1,
            flag = 0;
        while (flag < n) {
            index++;
            if (a % index == 0 || index % a == 0 || b % index == 0 || index % b == 0) {
                flag++;
            }
        }
        return (int) (index % mod);
    }

    /**
     * 911. 在线选举<br/>
     * 给你两个整数数组 persons 和 times 。在选举中，第i张票是在时刻为times[i]时投给候选人 persons[i]的。<br/>
     * 对于发生在时刻 t 的每个查询，需要找出在t 时刻在选举中领先的候选人的编号。<br/>
     * 在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。<br/>
     * Your TopVotedCandidate object will be instantiated and called as such:<br/>
     * TopVotedCandidate obj = new TopVotedCandidate(persons, times);<br/>
     * int param_1 = obj.q(t);
     */
    public class TopVotedCandidate{
        private int[] persons;
        private int[] times;
        public TopVotedCandidate(int[] persons, int[] times) {
            this.persons = persons;
            this.times = times;
        }

        public int q(int t) {
            int[] trueTimes = Arrays.stream(times).filter(time -> time <= t).toArray();
            List<Integer> truePersons = Arrays.stream(persons).boxed().collect(Collectors.toList()).subList(0, trueTimes.length);
            Map<Integer, Integer> resultMap = truePersons.parallelStream().collect(Collectors.toConcurrentMap(truePerson -> truePerson, truePerson -> 1, Integer::sum));

            int maxVote = resultMap.values().stream().max(Integer::compareTo).orElse(-1);
            Collections.reverse(truePersons);
            Set<Integer> existPerson = new HashSet<>(truePersons.size());
            int result = truePersons.stream().map(truePerson -> {
                if (existPerson.contains(truePerson)) {
                    return -1;
                }
                if (resultMap.get(truePerson) < maxVote) {
                    existPerson.add(truePerson);
                    return -1;
                } else {
                    return truePerson;
                }
            }).filter(item -> item != -1).findFirst().get();

            return result;
        }
    }

    /**
     * 1021. 删除最外层括号
     * <p>有效括号字符串为空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。</p>
     * <p>例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。</p>
     * <p>如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。</p>
     * <p>给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。</p>
     * <p>对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。</p>
     */
    public String removeOutterParentheses(String s) {
        char[] sChar = s.toCharArray();
        StringBuilder result = new StringBuilder();
        int left = 0;
        int right = 0;
        int flag = 0;

        for (int index=0; index < sChar.length; index++) {
            if (sChar[index] == '(') {
                left++;
            } else if (sChar[index] == ')') {
                right++;
            }
            if (left - right == 0) {
                left = right = 0;
                String primitiveStr = s.substring(flag, index + 1);
                result.append(primitiveStr, 1, primitiveStr.length() - 1);
                flag = index + 1;
            }
        }

        return result.toString();
    }

    /**
     * 1037. 有效的回旋镖
     * <p>给定一个数组 <strong>points</strong>，其中 <strong>points[i] = [xi, yi]</strong> 表示 <strong>X-Y</strong> 平面上的一个点，
     * 如果这些点构成一个 <strong>回旋镖</strong> 则返回 true 。</p>
     * <p><strong>回旋镖</strong> 定义为一组三个点，这些点 <strong>各不相同</strong> 且 <strong>不在一条直线上</strong> 。</p>
     *
     * @param points 坐标数组
     * @return 是否是回旋镖
     */
    public boolean isBoomerang(int[][] points) {
        // 如果有相同的点直接返回false
        if (points[0][0] == points[1][0] && points[0][1] == points[1][1]) {
            return false;
        } else if (points[1][0] == points[2][0] && points[1][1] == points[2][1]) {
            return false;
        } else if (points[0][0] == points[2][0] && points[0][1] == points[2][1]) {
            return false;
        }

        return (points[0][0] * points[1][1] - points[1][0] * points[0][1] +
                points[1][0] * points[2][1] - points[2][0] * points[1][1] +
                points[2][0] * points[0][1] - points[0][0] * points[2][1]) != 0;
    }

    /**
     * 1234. 替换子串得到平衡字符串
     * 有一个只含有'Q', 'W', 'E','R'四种字符，且长度为 n的字符串。
     * 假如在该字符串中，这四个字符都恰好出现n/4次，那么它就是一个「平衡字符串」。
     * 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
     * 你可以用和「待替换子串」长度相同的任何 其他字符串来完成替换。
     * 请返回待替换子串的最小可能长度。
     * 如果原字符串自身就是一个平衡字符串，则返回 0。
     * @param s 待处理的字符串
     * @return {待替换子串的最小可能长度}
     */
    public int balancedString(String s) {
        int minLen = 0;
        int maxLen = s.length() / 4;
        int q = 0,
            w = 0,
            e = 0,
            r = 0;
        for (int i=0; i<s.length(); i++) {
            switch (s.substring(i, i+1)){
                case "Q":
                    q += 1;
                    break;
                case "W":
                    w += 1;
                    break;
                case "E":
                    e += 1;
                    break;
                case "R":
                    r += 1;
                    break;
            }
        }
        if (q > w) {
            if (q > e) {
                if (q > r) {
                    // q
                }else {
                    // r
                }
            } else {
                if (e > r) {
                    // e
                }else {
                    // r
                }
            }
        } else {
            if (w > e) {
                if (w > r) {
                    // w
                }else {
                    // r
                }
            } else {
                if (e > r) {
                    // e
                }else {
                    // r
                }
            }
        }

        return minLen;
    }
}
